//
//  Problem4.swift
//  LeetCode
//
//  Created by zhulongiMac02 on 2019/11/27.
//  Copyright © 2019 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 4.给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

 你可以假设 nums1 和 nums2 不会同时为空。

 示例 1:

 nums1 = [1, 3]
 nums2 = [2]

 则中位数是 2.0
 示例 2:

 nums1 = [1, 2]
 nums2 = [3, 4]

 则中位数是 (2 + 3)/2 = 2.5
 */
class Problem4: NSObject {
    func solution() {
        let nums1 = [1, 2, 3, 4, 5, 6]
        let nums2 = [2, 3]
        
        print(findMedianSortedArrays(nums1, nums2))
    }
    
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        if nums1.count == 1 && nums2.count == 1 {
            return Double(nums1[0] + nums2[0]) / 2
        }
        if nums1.count == 0 {
            return nums2.count % 2 == 0 ? (Double(nums2[nums2.count / 2 - 1]) + Double(nums2[nums2.count / 2])) / 2: Double(nums2[nums2.count / 2])
        }
        
        if nums2.count == 0 {
            return nums1.count % 2 == 0 ? (Double(nums1[nums1.count / 2 - 1]) + Double(nums1[nums1.count / 2])) / 2: Double(nums1[nums1.count / 2])
        }
        
        let find1 = (nums1.count + nums2.count + 1) / 2
        let find2 = (nums1.count + nums2.count + 2) / 2
        print("find1 = ", find1)
        print("find2 = ", find2)
        
        
        let find1x = self.findX(nums1: nums1, i: 0, nums2: nums2, j: 0, x: find1)
        if find1 == find2 {
            return Double(find1x)
        } else {
            let find2x = self.findX(nums1: nums1, i: 0, nums2: nums2, j: 0, x: find2)
            print("find1x = ", find1x)
            print("find2x = ", find2x)
            return (Double(find1x) + Double(find2x)) / 2
        }
    }
    
    func findX(nums1:[Int], i: Int, nums2:[Int], j: Int, x: Int) -> Int {
        if i >= nums1.count {
            return nums2[j + x - 1]
        }
        if j >= nums2.count {
            return nums1[i + x - 1]
        }
        
        if x == 1 {
            return nums1[i] < nums2[j] ? nums1[i] : nums2[j]
        }
        
        
        // 1 4 7
        // 2 3 4 5 6 7 8 9 10 11 12 13 14
        // 1 2 3 4 4 5 6  7 7  8 9 10 11 12 13 14  x = 8
        var mindle1:Int = 0
        var nx = i + x / 2
        if (i + x / 2 - 1) < nums1.count {
            mindle1 = nums1[i + x / 2 - 1]
        } else {
            mindle1 = nums1[nums1.count - 1]
            nx = nums1.count - i
        }
        
        var mindle2:Int = 0
        var ny = j + x / 2
        if (j + x / 2 - 1) < nums2.count {
            mindle2 = nums2[j + x / 2 - 1]
        } else {
            mindle2 = nums2[nums2.count - 1]
            ny = nums2.count - j
        }
        
        if mindle1 < mindle2 {
            return self.findX(nums1: nums1, i: i + nx, nums2: nums2, j: j, x: x - nx)
        } else {
            return self.findX(nums1: nums1, i: i, nums2: nums2, j: j + ny, x: x - ny)
        }
    }
    
}
